package cn.edu.zzuli.search;

public class BinarySearch {

    public static void main(String[] args) {
        //二分查找，要求数组必须是有序的
        int arr[] = {1, 8, 10, 89, 1000, 1234};
        //System.out.println(binarySearch(arr,0, arr.length - 1, 2));

        System.out.println(interPolationSearch(arr, 0, arr.length - 1, 555));

    }

    /**
     * 二分查找
     * @param arr   要查询的数组
     * @param left  左边的索引
     * @param right 右边的索引
     * @param val   要查询的值
     * @return      返回index，-1 为未找到
     */
    public static int binarySearch(int[] arr, int left, int right, int val) {
        //递归出口，遍历完成但是没有找到值。
        if (left > right) {
            return -1;
        }

        int mid = (left + right) / 2;
        int midVal = arr[mid];

        if (val > midVal) {
            return binarySearch(arr, mid + 1, right, val);
        }else if (val < midVal) {
            return binarySearch(arr, left, mid - 1, val);
        }else {
            return mid;
        }

    }

    //插值查找
    public static int interPolationSearch(int[] arr, int left, int right, int findValue) {
        //防止越界
        if(left > right || findValue < arr[left] || findValue > arr[right]) {
            return -1;
        }

        //由于取整的关系， a*b/c 不等于 a/c*b
        int mid = left + (right - left) * (findValue - arr[left]) / (arr[right] - arr[left]);
        int midVal = arr[mid];
        if(findValue > midVal) {
            return interPolationSearch(arr, mid + 1, right, findValue);
        }else if(findValue < midVal) {
            return interPolationSearch(arr, left, mid - 1, findValue);
        }else {
            return mid;
        }
    }


}
